package com.linzm.leetcode.mid.tree.层次遍历;

import java.util.*;

/**
 * @Author zimingl
 * @Date 2023/2/20 23:43
 * @Description: 在每个树行中找最大值
 */
public class LargestValues515 {
    public static void main(String[] args) {
        LargestValues515 largestValues515 = new LargestValues515();
        List<Integer> list = largestValues515.largestValues(TreeNode.getTree());
        System.out.println(list);
    }

    private List<Integer> largestValues(TreeNode root) {
        if (root == null) return Collections.emptyList();
        List<TreeSet<Integer>> list = new ArrayList<>();
        dfs(root, list, 0);
        List<Integer> res = new ArrayList<>();
        for (TreeSet<Integer> treeSet : list) {
            res.add(treeSet.last());
        }
        return res;
    }

    private void dfs(TreeNode treeNode, List<TreeSet<Integer>> res, int depth) {
        if (treeNode == null) return;
        depth++;
        if (depth > res.size()) {
            TreeSet<Integer> list = new TreeSet<>();
            res.add(list);
        }
        res.get(depth - 1).add(treeNode.val);
        dfs(treeNode.left, res, depth);
        dfs(treeNode.right, res, depth);
    }
}
